


#include <stdio.h>

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
 struct TreeNode 
 {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
 };
typedef struct TreeNode BTNode;

typedef struct TreeNode* QDataType;
typedef struct QueueNode
{
	QDataType val;
	struct QueueNode* next;
} QNode;

typedef struct Queue
{
	int size;
	QNode* phead;
	QNode* ptail;
} Queue;

void QueueInit(Queue* pq)
{
	assert(pq);

	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

void QueueDestroy(Queue* pq)
{
	assert(pq);

	QNode* pcur = pq->phead;
	while (pcur)
	{
		QNode* pnext = pcur->next;
		free(pcur);

		pcur = pnext;
	}

	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);

	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(EXIT_FAILURE);
	}
	newnode->next = NULL;
	newnode->val = x;

	if (pq->ptail == NULL)
	{
		pq->phead = pq->ptail = newnode;
	}
	else
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}

	pq->size++;
}

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->phead);

	if (pq->phead->next == NULL)//pq->phead == pq->ptail
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	else
	{
		QNode* next = pq->phead->next;
		free(pq->phead);
		pq->phead = next;
	}

	pq->size--;
}

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->phead);

	return pq->phead->val;
}

int QueueSize(Queue* pq)
{
	assert(pq);

	return pq->size;
}

bool QueueEmpty(Queue* pq)
{
	assert(pq);

	return pq->size == 0;
}

int _isEvenOddTree(struct TreeNode* root)
{
	Queue q;
	QueueInit(&q);

	if (root->left)
		QueuePush(&q, root->left);
	if (root->right)
		QueuePush(&q, root->right);

	int level = 1;
	while (!QueueEmpty(&q))
	{
		int cur = QueueFront(&q)->val;
		int sz = QueueSize(&q);
		if (0 == (cur + level) % 2)
		{
			QueueDestroy(&q);
			return false;
		}

		for (int i = 0; i < sz - 1; ++i)
		{
			if (0 == (cur+level)%2)
			{
				QueueDestroy(&q);
				return false;
			}

			if (QueueFront(&q)->left)
				QueuePush(&q, QueueFront(&q)->left);
			if (QueueFront(&q)->right)
				QueuePush(&q, QueueFront(&q)->right);
			QueuePop(&q);

			int next = QueueFront(&q)->val;
			if (0 == (next + level) % 2)
			{
				QueueDestroy(&q);
				return false;
			}
			if (level % 2)
			{
				if (cur <= next)
				{
					QueueDestroy(&q);
					return false;
				}
			}
			else
			{
				if (cur >= next)
				{
					QueueDestroy(&q);
					return false;
				}
			}
			cur = QueueFront(&q)->val;
		}

		if (QueueFront(&q)->left)
			QueuePush(&q, QueueFront(&q)->left);
		if (QueueFront(&q)->right)
			QueuePush(&q, QueueFront(&q)->right);
		QueuePop(&q);

		++level;
	}

	QueueDestroy(&q);

	return true;
}

bool isEvenOddTree(struct TreeNode* root)
{
	if (0 == root->val % 2)
		return false;

	if (!(root->left || root->right) && root->val % 2)
		return true;

	return _isEvenOddTree(root);
}

BTNode* BuyNode(int x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	assert(node);

	node->val = x;
	node->left = NULL;
	node->right = NULL;

	return node;
}

BTNode* CreateBTree1(void)
{
	BTNode* n1 = BuyNode(1);
	BTNode* n2 = BuyNode(10);
	BTNode* n3 = BuyNode(4);
	BTNode* n4 = BuyNode(3);
	BTNode* n5 = BuyNode(7);
	BTNode* n6 = BuyNode(9);
	BTNode* n7 = BuyNode(12);
	BTNode* n8 = BuyNode(8);
	BTNode* n9 = BuyNode(6);
	BTNode* n10 = BuyNode(2);
	n1->left = n2, n1->right = n3;
	n2->left = n4;
	n3->left = n5, n3->right = n6;
	n4->left = n7, n4->right = n8;
	n5->left = n9;
	n6->right = n10;

	return n1;
}

BTNode* CreateBTree2(void)
{
	BTNode* n1 = BuyNode(5);
	BTNode* n2 = BuyNode(4);
	BTNode* n3 = BuyNode(2);
	BTNode* n4 = BuyNode(3);
	BTNode* n5 = BuyNode(3);
	BTNode* n6 = BuyNode(7);
	n1->left = n2, n1->right = n3;
	n2->left = n4, n2->right = n5;
	n2->left = n6;

	return n1;
}

BTNode* CreateBTree3(void)
{
	BTNode* n1 = BuyNode(5);
	BTNode* n2 = BuyNode(9);
	BTNode* n3 = BuyNode(1);
	BTNode* n4 = BuyNode(3);
	BTNode* n5 = BuyNode(5);
	BTNode* n6 = BuyNode(7);
	n1->left = n2, n1->right = n3;
	n2->left = n4, n2->right = n5;
	n3->left = n6;

	return n1;
}

BTNode* CreateBTree4(void)
{
	BTNode* n1 = BuyNode(7);
	BTNode* n2 = BuyNode(9);
	BTNode* n3 = BuyNode(5);
	BTNode* n4 = BuyNode(9);
	BTNode* n5 = BuyNode(13);
	n1->left = n2, n1->right = n3;
	n2->left = n4;
	n3->left = n5;

	return n1;
}

BTNode* CreateBTree5(void)
{
	BTNode* n1 = BuyNode(11);
	BTNode* n2 = BuyNode(18);
	BTNode* n3 = BuyNode(14);
	BTNode* n4 = BuyNode(3);
	BTNode* n5 = BuyNode(7);
	BTNode* n6 = BuyNode(18);
	BTNode* n7 = BuyNode(6);
	n1->left = n2, n1->right = n3;
	n2->left = n4, n2->right = n5;
	n5->left = n6;
	n6->left = n7;

	return n1;
}

int main()
{
	BTNode* root1 = CreateBTree1();
	BTNode* root2 = CreateBTree2();
	BTNode* root3 = CreateBTree3();
	BTNode* root4 = CreateBTree4();
	BTNode* root5 = CreateBTree5();

	int ret1 = _isEvenOddTree(root1);
	int ret2 = _isEvenOddTree(root2);
	int ret3 = _isEvenOddTree(root3);
	int ret4 = _isEvenOddTree(root4);
	int ret5 = _isEvenOddTree(root5);
	printf("ret1:%d\n", ret1);
	printf("ret2:%d\n", ret2);
	printf("ret3:%d\n", ret3);
	printf("ret4:%d\n", ret4);
	printf("ret5:%d\n", ret5);

	return 0;
}